//给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
//
// 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
//
//
//
// 示例 1：
//
//
//输入：nums = [100,4,200,1,3,2]
//输出：4
//解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
//
// 示例 2：
//
//
//输入：nums = [0,3,7,2,5,8,4,6,0,1]
//输出：9
//
//
//
//
// 提示：
//
//
// 0 <= nums.length <= 10⁵
// -10⁹ <= nums[i] <= 10⁹
//
//
// Related Topics 并查集 数组 哈希表 👍 1697 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
//? set解法
function longestConsecutive(nums: number[]): number {
    //? set解法
    let num_set: Set<number> = new Set();
    for (const num of nums) {
        num_set.add(num);
    }

    let longestStreak = 0;

    for (const num of num_set) {
        //? 不含有比他小1的数 否则一定此次运算不会成为结果
        if (!num_set.has(num - 1)) {
            let currentNum = num;
            let currentStreak = 1;
            //? 开始往后找
            while (num_set.has(currentNum + 1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;

};
//leetcode submit region end(Prohibit modification and deletion)
//? 解法二 先排序 再比较
function longestConsecutive2(nums: number[]): number {
    if (nums.length === 0 || !Array.isArray(nums)) return 0;
    nums.sort((a,b) => a-b);
    let max = -Infinity;
    let times = 1;
    for (let j = 1; j < nums.length; j++) {
        if (nums[j] === nums[j-1] + 1) {
            times++;
        } else if(nums[j] === nums[j-1]) {
            continue;
        } else {
            max = Math.max(max, times);
            times = 1;
        }
    }
    return Math.max(times, max);


};
//? 解法三 并查集
class UnionFind {
    parent: any[]
    rank: any[]
    size: any[]
    constructor(size) {
        this.parent = [];
        this.rank = [];
        this.size = []; // 记录以当前节点为根节点的树的节点个数
        for (let i = 0; i < size; i++) {
            this.parent[i] = i;
            this.rank[i] = i;
            this.size[i] = 1;
        }
    }
    find(x) {
        if (x === this.parent[x]) {
            return x;
        }
        this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const pX = this.find(x);
        const pY = this.find(y);
        if (pX === pY) return;
        if (this.rank[pX] > this.rank[pY]) {
            this.parent[pY] = pX;
            this.size[pX] += this.size[pY];
        } else if (this.rank[pX] < this.rank[pY]) {
            this.parent[pX] = pY;
            this.size[pY] += this.size[pX];
        } else {
            this.parent[pY] = pX;
            this.size[pX] += this.size[pY];
            this.rank[pX] += 1;
        }
    }
    getMaxCount() {
        let max = 1;
        for (let i = 0; i < this.size.length; i++) {
            if (this.parent[i] === i) {
                max = Math.max(max, this.size[i]);
            }
        }
        return max;
    }
}
function longestConsecutive3(nums: number[]): number {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    const n = nums.length;
    if (n === 0 || n === 1) {
        return n;
    }
    const map = new Map();
    const uf = new UnionFind(n);
    for (let i = 0; i < n; i++) {
        if (map.has(nums[i])) continue;
        if (map.has(nums[i] - 1)) {
            uf.union(i, map.get(nums[i] - 1));
        }
        if (map.has(nums[i] + 1)) {
            uf.union(i, map.get(nums[i] + 1));
        }
        map.set(nums[i], i);
    }
    return uf.getMaxCount();
};
